package com.company.剑指offer每日刷题.专项版;

import java.util.*;

/**
 * 题目：剑指 Offer II 007. 数组中和为 0 的三个数
 * <p>
 * 给定一个包含 n 个整数的数组nums，判断nums中是否存在三个元素a ，b ，c ，使得a + b + c = 0 ？请找出所有和为 0 且不重复的三元组。
 * 示例 1：
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * <p>
 * 提示：
 * 0 <= nums.length <= 3000
 * -105 <= nums[i] <= 105
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/1fGaJU
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ThreeSum {

    public static void main(String[] args) {
        ThreeSum obj = new ThreeSum();
        List<List<Integer>> lists = obj.threeSum1(new int[]{-1, 0, 1, 2, -2, -2, -1, 4});
        for (List<Integer> list : lists) {
            System.out.println(list.toString());
        }
    }

    /**
     * 方法1：遍历法
     * 思路：用三个循环分别固定三个数，遍历收集所有为0的结果
     * 去除重复：
     * 其中将得到的list进行排序后，转化为字符串，用HashSet检查重复。
     * 时间复杂度：O(n^3) (超时，不推荐)
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        HashSet<String> tempSet = new HashSet<>();
        for (int x = 0; x < nums.length - 2; x++) {
            for (int y = x + 1; y < nums.length - 1; y++) {
                for (int z = y + 1; z < nums.length; z++) {
                    if (0 == nums[x] + nums[y] + nums[z]) {
                        List<Integer> integers = Arrays.asList(nums[x], nums[y], nums[z]);
                        Collections.sort(integers);
                        String joinStr = integers.toString();
                        if (!tempSet.contains(joinStr)) {
                            res.add(integers);
                            tempSet.add(joinStr);
                        }
                    }
                }
            }
        }
        return res;
    }

    /**
     * 方法2：双指针法
     * 思路：使用双指针法的前提是我们的数组是有序的。所以先做一个排序
     * 固定一个数i，然后从后面剩下的数中通过双指针法确定两个数，
     * 去重优化可以通过跳过已经出现过的数字，移动i或者left、right指针的位置的方式实现
     */
    public List<List<Integer>> threeSum1(int[] nums) {
        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }
        //排序
        Arrays.sort(nums);
        //查找结果
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i >= 1 && nums[i - 1] == nums[i])
                continue;
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] + nums[i] < 0) {
                    left++;
                } else if (nums[left] + nums[right] + nums[i] > 0) {
                    right--;
                } else {
                    List<Integer> list = Arrays.asList(nums[i], nums[left], nums[right]);
                    res.add(list);
                    while (left < right && nums[left] == nums[++left]) ;
                    while (left < right && nums[right] == nums[--right]) ;
                }
            }
        }
        return res;
    }

}
